Towards an efficient weighted random walk domination

Abstract

In this paper, we propose and study a new problem called the weighted random walk domination. Given a weighted graph G(V, E) and a budget B of the weighted random walk, it aims to find a k-size set S, which can minimize the total costs of the remaining nodes to access S through the weighted random walk, which is bounded by B. This problem is critical to a range of real-world applications, such as advertising in social networks and telecommunication base station selection in wireless sensor networks. We first present a dynamic programming based greedy method (DpSel) as a baseline. DpSel is time-consuming when |V | is huge. Thus, to overcome this drawback, we propose a matrix-based greedy meth..